package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/2/29.
 */
public class LC372 {

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * @return:
     */

    int base = 1337;

    // 计算 a 的 k 次方然后与 base 求模的结果
    int mypow(int a, int k) {
        if (k == 0) return 1;
        a %= base;

        if (k % 2 == 1) {
            // k 是奇数
            return (a * mypow(a, k - 1)) % base;
        } else {
            // k 是偶数
            int sub = mypow(a, k / 2);
            return (sub * sub) % base;
        }
    }

    public int superPowRecur(int a, int[] b, int blen) {
        if (blen < 0) return 1;
        int last = b[blen];

        int part1 = mypow(a, last);
        int part2 = mypow(superPowRecur(a, b, --blen), 10);
        // 每次乘法都要求模
        return (part1 * part2) % base;
    }

    public int superPow(int a, int[] b) {
        return superPowRecur(a, b, b.length - 1);
    }

    public static void main(String[] args) {
        LC372 an = new LC372();
        int[] b = InputUtil.toIntegerArray("[1,0]");
        System.out.println(an.superPow(2, b));
    }
}
